The development of computer programs for microcomputers is often an expensive and time-consuming enterprise. To recover the development cost of such programs it is important to the developer that each user pay for the programs he uses. This is often difficult to accomplish in practice, because it is generally easy for users to make multiple copies of the programs for non-paying users, and easy for competitors to repackage and distribute valuable programs at a fraction of the original developer's cost. The development of highly human-engineered systems which can be used by unskilled microcomputer owners has been inhibited by the realization that a market price high enough to cover costs will also be high enough to attract pirating and covert distribution of unauthorized copies. This problem is made worse by the fact that microcomputers are inexpensive lightweight devices which can be taken apart and analyzed in secret by their owners who may be numerous and anonymous.
Microcomputers generally contain one or more integrated circuit microprocessors that execute the program instructions one byte at a time. (A byte is usually 8 bits or 16 bits but other byte sizes may be used in the present invention). These microprocessors are usually interchangeable stock components which are available from many vendors. This interchangeability makes it easy for a competitor to plagiarize proprietary programs by using similar but unauthorized microprocessors. One method of preventing such theft of proprietary programs is to alter each microprocessor and the programs which accompany it so that neither the microprocessors nor the programs are interchangeable. This can be accomplished by enciphering each program in a different cipher so that each program can be deciphered and executed only by the authorized microprocessor that accompanies it in the microcomputer. The main disadvantages of this approach are that prior-art encryption methods are either not sufficiently secure against cryptanalyst attack, or require too much space on the microprocessor chip, and/or are too slow when used for this purpose. The following prior-art encryption methods have one or more of these disadvantages.
Block cipher systems have been developed for protecting digital information during transmission over communication networks. Some of these systems are extremely secure and are suitable for such data as financial transactions which must be immune from cryptanalyst attack. One method of providing such high security is to use alternating substitution and transportion as described in "Communication Theory of Secrecy Systems" by C. E. Shannon, Bell System Technical Journal, Vol. 28, pages 711-713, October 1949. Further teachings on such block cipher systems may be found in "Cryptography and Computer Privacy" by Horst Feistel, Scientific American, Vol. 228, No. 5, pages 15-23, May 1973. Several inventions have made use of these teachings, for example the systems disclosed in U.S. Pat. Nos. 3,789,359 and 3,958,081 issued Mar. 19, 1974 and May 18, 1976 respectively. These block cipher systems are suitable for protecting valuable software used in microprocessors as disclosed in copending application Ser. No. 750,009 filed Dec. 13, 1976, now abandoned. A deciphering processor using such a block cipher is highly secure, but is complex, costly and slow for the kind of microcomputers contemplated for use with the present invention.
Simple low-cost stream cipher systems are frequently used for enciphering digital communications data by combining in various ways the message being transmitted with a long stream of quasi-random bits. This stream of bits is generated by a random number generator from a cipher key or "seed". An example of such a system may be found in U.S. Pat. No. 3,911,216 issued Oct. 7, 1975. If a stream cipher method were used to protect microcomputer programs, the deciphering circuitry would not be able to decipher the whole program as a long stream and then execute it, because space limitations prevent the whole deciphered program from being stored on the microprocessor chip. Storing it external to the microprocessor is futile, because the wiring of the microcomputer is accessible to users. Deciphering the program as it executes is not practical either (using a stream chiper), because programs do not generally execute and address data in a strict address sequence, but instead contain many loops and jumps. Hence a program enciphered in address sequence cannot be deciphered as a stream. To recompute a portion of the random bit stream every time the address sequence changed would be a slow process, and would be prohibitively slow if different portions of the random bit stream had to be recomputed for each instruction executed. For these reasons such stream ciphers are not practical for protecting programs which are deciphered as they are executed in a microprocessor.
Another prior-art encryption method is monoalphabetic substitution. In such a system each byte of the program would be replaced with a substitute byte. Each byte of the enciphered program would be deciphered when needed by a simple table-lookup using a small substitution table which is part of the circuitry on the microprocessor chip. This method has several advantages: it is simple, fast, does not take too much space on the chip, and may proceed in any instruction sequence. Unfortunately, monoalphabetic substitution is not difficult to break, and hence offers little security for the program.
Other prior-art encryption methods share one or more of the disadvantages already mentioned. Hence the prior art does not provide a secure cryptographic system which is suitable for protecting programs which are deciphered one byte at a time as the program executes, by an inexpensive single-chip microprocessor in a computer with easily accessible wiring.